//
// Created by dsy on 2022/12/27.
//

#include "common.h"

/******* 堆排序 *******/

void PercDown(int A[], int p, int N)
{
    int parent, child, tmp;
    tmp = A[p];
    for (parent = p; parent * 2 + 1 < N; parent = child) {
        child = parent * 2 + 1;
        if (child != N - 1 && A[child] < A[child + 1])
            child++;
        if (tmp >= A[child]) break;
        else A[parent] = A[child];
    }
    A[parent] = tmp;
}

void HeapSort(int A[], int N)
{
    int i, tmp;

    for (i = N / 2 - 1; i >= 0; i--) // 先将整个数组初始化为一个最大堆
        PercDown(A, i, N);

    for (i = N - 1; i > 0; i--) { // 然后每次把最大堆的顶元素与尾元素交换
        tmp = A[0];
        A[0] = A[i];
        A[i] = tmp;
        PercDown(A, 0, i); // 再把去除尾元素的堆更新为最大堆，以此类推。从后到前生成非递减序列的排序。
    }
}

/******* 快速排序 *******/

void QuickSort(int A[], int N) // 统一接口
{
    QSort(A, 0, N - 1);
}

void QSort(int *arr, int low, int high)
{
    if (low < high) {
        int i = low;
        int j = high;
        int k = arr[low];
        while (i < j) {
            while (i < j && arr[j] >= k)     // 从右向左找第一个小于k的数
            {
                j--;
            }

            if (i < j) {
                arr[i++] = arr[j];
            }

            while (i < j && arr[i] < k)      // 从左向右找第一个大于等于k的数
            {
                i++;
            }

            if (i < j) {
                arr[j--] = arr[i];
            }
        }

        arr[i] = k;

        // 递归调用
        QSort(arr, low, i - 1);     // 排序k左边
        QSort(arr, i + 1, high);    // 排序k右边
    }
}